package 剑指offer;

import 抽象数据类型.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static 抽象数据类型.TreeNode.buildTree;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-25
 */
public class 在二叉树中找到两个节点的最近公共祖先 {
    public static void main(String[] args) {
        Integer[] str = new Integer[]{27, 32, 34, 19, 41, 17, 18, 9, 14, 44, 39, null, null, 24, 30, null,
                null, null, 2, 7, 42, 28, 36, null, null, 11, 6, null, 1, null, null, null, 31, 16, 4, 22, 33,
                null, null, null, 5, 10, 15, 37, 12, 8, null, 35, 3, null, 23, 21, null, null, null, 29, null,
                null, null, 40, null, null, null, null, null, null, null, null, null,
                13, 43, null, null, null, null, null, null, 25, 20, null, null, 38, null, 26};
        // String[] str = {"1", "2", "2", null, null, "4", "4"};
        List<Integer> asList = Arrays.asList(str);
        TreeNode treeNode = buildTree(new ArrayList<>(asList));

        System.out.println(lowestCommonAncestor(treeNode, 32, 38));
    }

    /**
     * @param root TreeNode类
     * @param o1   int整型
     * @param o2   int整型
     * @return int整型
     */
    public static int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        // write code here
        if (root != null && (has(root, o1) && (Integer) root.val == o2) || (has(root, o2) &&(Integer) root.val == o1)) {
            return (Integer) root.val;
        } else if (root != null && ((has(root.left, o1) && has(root.right, o2)) || has(root.right, o1) && has(root.left, o2))) {
            return (Integer) root.val;
        } else if (root != null && (has(root.left, o1) && has(root.left, o2))) {
            return lowestCommonAncestor(root.left, o1, o2);
        } else if (root != null && (has(root.right, o1) && has(root.right, o2))) {
            return lowestCommonAncestor(root.right, o1, o2);
        }
        return -1;
    }

    public static boolean has(TreeNode root, int o) {
        if (root == null) {
            return false;
        }
        if ((Integer) root.val == o) {
            return true;
        }
        return has(root.left, o) || has(root.right, o);
    }
}
